#include "headfiles.h"

using namespace std;

// check whether the binary tree contains the node
// return true if contains; return false otherwise
bool containNode(NODE *root, NODE *n) {
	if (root == NULL) {
		return false;
	}

	if (root == n) {
		return true;
	}
	else {
		return containNode(root->left, n) || containNode(root->right, n);
	}
}

NODE * findCommonAncestor(NODE *root, NODE *n1, NODE *n2) {
	if (root == NULL ||
		n1 == NULL ||
		n2 == NULL) {
		return NULL;
	}

	if (((root == n1) && containNode(root, n2)) ||
		((root == n2) && containNode(root, n1))) {
		return root;
	}
	
	if (containNode(root->left, n1)) {
		if (containNode(root->left, n2)) {
			return findCommonAncestor(root->left, n1, n2);
		}
		else if (containNode(root->right, n2)) {
			return root;
		}
		else {
			return NULL;
		}
	}
	else if (containNode(root->right, n1)) {
		if (containNode(root->right, n2)) {
			return findCommonAncestor(root->right, n1, n2);
		}
		else if (containNode(root->left, n2)) {
			return root;
		}
		else {
			return NULL;
		}
	}
	else {
		return NULL;
	}
}

// Contains both nodes
void containNodesRecur(NODE *root, NODE *p, NODE *q, int *num_nodes) {
    if (root == NULL) {
        return;
    }

    if (root == p) {
        (*num_nodes)++;
    }

    if (root == q) {
        (*num_nodes)++;
    }
    else {
        containNodesRecur(root->left, p, q, num_nodes);
        containNodesRecur(root->right, p, q, num_nodes);
    }

    return;
}

int containNodes(NODE *root, NODE *p, NODE *q) {
    int node_num = 0;
    containNodesRecur(root, p, q, &node_num);

    return node_num;
}

